package algorithm.leetcode.I801to1000;

/**
 * 爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：
 * 爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。
 * 每次抽取都是独立的，其结果具有相同的概率。
 * 当爱丽丝获得不少于 K 分时，她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少？
 *
 * 思路：逆向DP
 * 令dp[x]为点数和为x时获胜(点数不超过N)的概率
 *
 * 首先,由于这个停止条件,点数可以从0点到K+W-1分
 * 其次,还是因为这个停止条件,当点数x<K时还要抽,所以当得分x>=K的时候
 *      1. K<=x<=MIN(N, K+W-1),这就是赢了,dp[x]=1
 *      2. x>MIN(N, K+W-1),这是输了,dp[x]=0,包含两种情况:
 *          2.1 "爆了",即点数超过N,也就是N<K+W-1,那么赢的概率是0
 *          2.2 不可能得到的点数,即K+W-1<N,这是赢的情况,即概率为1
 * 再次,讨论x<K的时候,需要再抽一次,而抽取到的数的概率是平均的,所以在这个情况下的状态转移方程为
 *      dp[x]=(dp[x+1]+dp[x+2]+...+dp[x+W])*1/W
 * 最后,对"再次"中的循环进行优化,求dp[0]
 */

public class Q837 {
    public double new21Game(int N, int K, int W) {
        if (N == 0 || K == 0) return 1.0;

        double[] dp = new double[K+W];

        for (int i = dp.length-1; i >= 0; i--) {
            if (i <= W+K-1 && i >= K && i <= N) {
                dp[i] = 1.0;
            } else if (i == K-1) {
                dp[i] = Math.min(N-K+1, W)*1.0/W;
            } else if (i < K-1) {
                dp[i] = dp[i+1] - (dp[i+W+1]-dp[i+1])/W;
//                for (int i1 = 1; i1 <= W; i1++) {
//                    dp[i] += dp[i+i1]/W;
//                }
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        Q837 ets = new Q837();
        double res = ets.new21Game(21, 17, 10);
        System.out.println(res);
    }
}
